import math
import random

def assign_cluster(x, c):
    min_dist = float('inf')
    cluster_idx = 0
    for i, center in enumerate(c):
        # 计算欧氏距离
        dist = math.sqrt(sum([(a - b)**2 for a, b in zip(x, center)]))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx

def Kmeans(data, k, epsilon=1e-6, iteration=100):
    n_samples = len(data)
    n_features = len(data[0]) if n_samples > 0 else 0
    
    # 初始化聚类中心（随机选择k个样本）
    centers = random.sample(data, k)
    
    for _ in range(iteration):
        # 分配每个样本到最近的聚类中心
        clusters = [[] for _ in range(k)]  # 存储每个聚类的样本
        for x in data:
            idx = assign_cluster(x, centers)
            clusters[idx].append(x)
        
        # 计算新的聚类中心
        new_centers = []
        for cluster in clusters:
            if not cluster:  # 防止空聚类（可根据需求调整策略）
                new_centers.append(random.choice(data))  # 随机选一个样本作为中心
                continue
            # 计算每个特征的均值
            center = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            new_centers.append(center)
        
        # 判断是否收敛（所有中心变化小于epsilon）
        max_change = 0.0
        for old, new in zip(centers, new_centers):
            change = math.sqrt(sum([(a - b)** 2 for a, b in zip(old, new)]))
            if change > max_change:
                max_change = change
        if max_change < epsilon:
            break
        
        centers = new_centers
    
    # 生成最终标签
    labels = [assign_cluster(x, centers) for x in data]
    return centers, labels